Search for: All records

We study fundamental theoretical aspects of probabilistic roadmaps (PRM) in the finite time (non-asymptotic) regime. In particular, we investigate how completeness and optimality guarantees of the approach are influenced by the underlying deterministic sampling distribution $${\X}$$ and connection radius $${r>0}$$. We develop the notion of $${(\delta,\epsilon)}$$-completeness of the parameters $${\X, r}$$, which indicates that for every motion-planning problem of clearance at least $${\delta>0}$$, PRM using $${\X, r}$$ returns a solution no longer than $${1+\epsilon}$$ times the shortest $${\delta}$$-clear path. Leveraging the concept of $${\epsilon}$$-nets, we characterize in terms of lower and upper bounds the number of samples needed to guarantee $${(\delta,\epsilon)}$$-completeness. This is in contrast with previous work which mostly considered the asymptotic regime in which the number of samples tends to infinity. In practice, we propose a sampling distribution inspired by $${\epsilon}$$-nets that achieves nearly the same coverage as grids while using significantly fewer samples.